دانشگاه علم و هنر

وابسته به جهاد دانشگاهی

 

پایان‌نامه کارشناسی ارشد دانشکده فنی و مهندسی

گروه کامپیوتر

 

عنوان:

ارزیابی برخی الگوریتم‌های کنترل همروندی در سیستم مدیریت پایگاه داده‌ها، از طریق مدل‌سازی با پتری رنگی

 

استاد راهنما:

دکتر فاطمه سعادت‌جو

 

استاد مشاور:

مهندس محمد علی سعادت‌جو

 

شهریور 1393

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود

(در فایل دانلودی نام نویسنده موجود است)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

فهرست مطالب

عنوان                                                                                                                                            صفحه

فصل اول: مقدمه

1-1- مقدمه. 2

1-2- ساختار پایان‌نامه. 4

فصل دوم: پیشینه‌ی تحقیق

مقدمه. 7

2-1- اهمیت الگوریتم‌های کنترل همروندی پایگاه داده‌ها 7

2-2- برخی از انواع پایگاه داده‌ها 8

2-3- انواع روش‌های پیاده‌سازی و مدل‌سازی الگوریتم‌های کنترل همروندی.. 9

2-3-1- پیاده‌سازی در مقیاس کوچک… 9

2-3-2- مدل‌سازی و شبیه‌سازی توسط مدل مارکف.. 11

2-3-3- مدل‌سازی و شبیه‌سازی توسط شبکه‌های پتری.. 12

2-4- پارامترهای ارزیابی. 14

2-4-1- پارامترهای منابع سیستم 14

2-4-2- پارامترهای حجم کاری.. 15

2-5- پارامترها و آزمایش‌های انجام شده 16

2-6- برخی از مزایا و معایب روش‌های مدل‌سازی و شبیه‌سازی.. 18

2-7- لزوم انجام تحقیق. 20

فصل سوم: تکنیک‌های کنترل همروندی

مقدمه. 22

3-1- تکنیک‌های کنترل همروندی و انواع آن‌ها 22

3-2- تکنیک‌های قفل‌گذاری و انواع آن‌ها 23

3-2-1- تعریف قفل. 24

3-2-2- اندازه‌های واحد قفل‌شدنی. 24

3-2-3- ساختار قفل. 25

3-2-4- مثالی برای لزوم قفل‌گذاری.. 26

3-2-5- مدیر قفل و مراحل انجام شده برای قفل‌گذاری.. 27

3-2-6- نحوه در اختیار قرار دادن قفل توسط مدیر قفل. 28

3-2-7- قفل چند اسلوبی. 28

3-2-7-1- ماتریس همایندی یا سازگاری قفل‌های چند اسلوبی. 28

3-2-7-2- پروتکل قفل چند اسلوبی برای یک تراکنش.. 29

3-2-7-3- تغییر قفل. 30

3-2-7-4- قفل چند اسلوبی و توالی‌پذیری.. 30

3-2-7-5- خصوصیات قفل چند اسلوبی. 30

3-2-8- تکنیک قفل‌گذاری دو مرحله‌ای مبنایی. 30

3-2-8-1- مشکلات تداخل کنترل نشده 31

3-2-8-2- خصوصیات و مشکلات 2PL مبنایی. 32

3-2-8-3- تغییر قفل در پروتکل 2PL. 33

3-2-8-4- تأثیرعملیات درج در کنترل همروندی.. 33

3-2-8-5- تأثیرعملیات حذف در کنترل همروندی.. 33

3-3- بن‌بست.. 34

3-3-1- راه حل‌های مشکل بن‌بست.. 35

3-3-2- تکنیک‌های زمان‌مهر. 36

3-3-2-1- الگوریتم WD.. 37

3-3-2-2- الگوریتم WW… 37

3-3-2-3- خصوصیات الگوریتم WD و WW… 37

فصل چهارم: شبکه‌های پتری

مقدمه. 39

4-1- مختصری در مورد شبکه‌های پتری.. 39

4-2- تفاوت UML و پتری.. 39

4-3- تاریخچه شبکه‌های پتری.. 40

4-4- ویژگی‌های شبکه‌های پتری.. 40

4-5- اجزای شبکه‌ی پتری.. 40

4-5-1- تعریف اجزای شبکه‌ی پتری.. 41

4-5-2- وظایف اجزای شبکه‌ی پتری.. 41

4-6- تعریف چهارگانه شبکه‌های پتری.. 42

4-7- گراف شبکه پتری.. 42

4-8- چند مثال از گراف شبکه پتری.. 43

4-9- رفتار شبکه‌های پتری.. 43

4-10- گذار توانا 44

4-11- مثالی از اجرای یک شبکه پتری.. 44

4-12- قوانین مربوط به فایر شدن گذار، در شبکه پتری.. 45

4-13- شبکه‌های پتری به بن‌بست رسیده، زنده و غیر زنده 46

4-14- انواع شبکه‌های پتری و نحوه‌ی نشانه‌گذاری آن‌ها 47

4-15- فلوچارت‌ها و شبکه‌های پتری.. 47

4-16- انواع پتری.. 48

4-16-1- شبکه پتری رنگی. 48

4-16-2- شبکه پتری زمانی. 49

4-16-3- شبکه پتری سلسله مراتبی. 50

فصل پنجم: نحوه‌ی مدل‌سازی مکانیزم‌های 2PL، WW و WD با پتری رنگی

مقدمه. 52

5-1- مختصری در مورد مدل‌سازی مکانیزم‌های 2PL، WW و WD.. 52

5-1-1- مدل 2PL. 52

5-1-2- مدل‌های WW و WD.. 53

5-2- مجموعه‌های رنگ… 53

5-2-1- مجموعه‌های رنگ در مدل 2PL. 53

5-2-2- مجموعه‌های رنگ در مدل‌های WW و WD.. 54

5-2-3- توضیحات مجموعه‌های رنگ… 55

5-3- نشانه‌گذاری اولیه. 58

5-3-1- نشانه‌گذاری اولیه در مدل 2PL. 58

5-3-2- نشانه‌گذاری اولیه در مدل‌های WW و WD.. 59

5-3-3- توضیحات نشانه‌گذاری اولیه. 59

5-4- متغیرها 61

5-4-1- متغیرهای مدل 2PL. 61

5-4-2- متغیرهای مدل‌های WW و WD.. 62

5-5- شرح توابع مدل و عملکردهای آن‌ها 62

5-5-1- شرح توابع مشترک بین مدل‌های 2PL، WW و WD.. 63

5-5-2- شرح توابع مدل 2PL. 63

5-5-3- شرح توابع مدل‌های WW و WD.. 76

5-6- اولویت‌های معین شده برای تعیین فایر شدن گذار مورد نظر از بین گذارهای فعال. 72

5-7- نحوه‌ی مدل‌سازی‌ها 73

5-7-1- نحوه مدل‌سازی مدل 2PL. 73

5-7-2- نحوه مدل‌سازی مدل‌های WW و WD.. 75

فصل ششم: ارزیابی مدل‌های 2PL، WW و WD

مقدمه. 79

6-1- مختصری در مورد اهمیت ارزیابی پایگاه داده‎ها 79

6-2- پارامتر تعداد تراکنش‌های وارد شونده به سیستم 80

6-2-1- بررسی مدل 2PL. 80

6-2-2- بررسی مدل WW. 80

6-2-3- بررسی مدل WD.. 81

6-2-4- مقایسه‌ی مدل‌های 2PL، WW و WD براساس پارامتر تعداد تراکنش‌ها 82

6-3- پارامتر تعداد دستورات هر تراکنش.. 83

6-3-1- بررسی مدل 2PL. 83

6-3-2- بررسی مدل WW… 84

6-3-3- بررسی مدل WD.. 85

6-3-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد دستورات تراکنش‌ها 86

6-4- پارامتر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها 88

6-4-1- بررسی مدل 2PL. 88

6-4-2- بررسی مدل WW… 89

6-4-3- بررسی مدل WD.. 90

6-4-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها 91

6-5- پارامتر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک.. 92

6-5-1- بررسی مدل 2PL. 92

6-5-2- بررسی مدل WW… 93

6-5-3- بررسی مدل WD.. 94

6-5-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک.. 96

6-6- نتیجه‌گیری.. 97

6-7- پیشنهادات.. 100

مراجع. 102

فهرست جدول‌ها

عنوان جدول                                                                                                                                 صفحه

جدول1-1- پارامترهای مورد نظر برای ارزیابی مدل‌ها در این پایان‌نامه. 4

جدول2-1- آزمایش‌های مورد نظر برای ارزیابی مدل‌ها در این پایان‌نامه. 18

جدول 3-1- مزایا و معایب اندازه‌ی واحد قفل‌شدنی. 25

جدول 3-2- نمایش لزوم قفل‌گذاری.. 26

جدول 3-3- نمایش ناحیه کاری.. 27

جدول 3-4- ماتریس همایندی.. 29

جدول 3-5- سازگاری قفل‌های چند اسلوبی. 29

جدول 5-1- توضیحات مربوط به مجموعه‌های رنگی. 55

جدول 5-2- توضیحات مربوط به نشانه‌گذاری‌های اولیه. 60

جدول 5-3- پارامترهای ورودی تابع checklock برای مدل 2PL. 64

جدول 5-4- پارامترهای خروجی تابع checklock برای مدل 2PL. 65

جدول 5-5- پارامترهای ورودی تابع checklock برای مدل‌های WW و WD.. 68

جدول 5-6- پارامترهای خروجی تابع checklock برای مدل‌های WW و WD.. 69

جدول6-1- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل 2PL. 80

جدول 6-2- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل WW… 81

جدول 6-3- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل WD.. 82

جدول 6-4- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل 2PL. 84

جدول 6-5- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل WW… 85

جدول 6-6- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل WD.. 86

جدول 6-7- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل 2PL. 88

جدول 6-8- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل WW… 89

جدول 6-9- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل WD.. 90

جدول 6-10- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل 2PL. 92

جدول 6-11- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل WW.. 93

جدول 6-12- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل WD.. 95

 

فهرست شکل‌ها

عنوان شکل                                                                                                                                  صفحه

شکل 3-1- عملیات مدیر قفل و مدیر تراکنش.. 27

شکل 3-2- پروتکل 2PL و لحظه قفل. 31

شکل 3-3- نمونه‌ای از نحوه رخ دادن بن‌بست.. 34

شکل 3-4- مثال برای بن‌بست.. 35

شکل 4-1- اجزای شبکه‌ی پتری.. 40

شکل 4-2- عملکرد اجزای شبکه پتری.. 41

شکل 4-3- گراف شبکه پتری.. 42

شکل 4-4- مثال سیستم عابر بانک با گراف شبکه پتری.. 43

شکل 4-5- مثال تابع y=f(x) با گراف شبکه پتری.. 43

شکل 4-6- مثالی از نشانه‌گذاری یک مکان. 43

شکل 4-7- مثالی برای یک گذار توانا و یک گذار غیر توانا 44

شکل 4-8- مثالی از اجرای یک شبکه پتری و نشانه‌گذاری اولیه آن. 44

شکل 4-9- مثالی از اجرای یک شبکه پتری و M₀ آن. 45

شکل 4-10- مثالی از اجرای یک شبکه پتری و M₁ آن. 45

شکل 4-11- مثالی از اجرای یک شبکه پتری و M₂ آن. 45

شکل 4-12- مثالی از گراف شبکه پتری، قبل و بعد از فایر شدن. 46

شکل 4-13- مثالی از گراف شبکه پتری، قبل و بعد از فایر شدن. 46

شکل 4-14- یک شبکه پتری که دچار بن‌بست شده 46

شکل 4-15- انواع شبکه‌های پتری و نحوه‌ی نشانه‌گذاری آن‌ها 47

شکل 4-16- مدل‌سازی گره‌های تصمیم‌گیریِ فلوچارت با شبکه پتری.. 47

شکل 4-17- مدل‌سازی فلوچارت با شبکه پتری.. 48

شکل 4-18- شبکه پتری سلسله مراتبی. 50

شکل 4-19- مدل‌سازی مسئله ممانعت دو جانبه با شبکه پتری.. 50

شکل 5-1- ماژول سطح بالا از مدل 2PL به صورت سلسله مراتبی، برای سه تراکنش.. 73

شکل 5-2- ماژول سطح بالا از مدل 2PL به صورت سلسله مراتبی، برای دو تراکنش.. 74

شکل 5-3- ماژول مربوط به تراکنش T1 از مدل 2PL به صورت سلسله مراتبی. 74

شکل 5-4- ماژول سطح بالا از مدل‌های WW و WD به صورت سلسله مراتبی، برای سه تراکنش.. 75

شکل 5-5- ماژول مربوط به تراکنش T1 از مدل‌های WW و WD به صورت سلسله مراتبی، برای سه تراکنش   76

شکل 5-6- ماژول سطح بالا از مدل‌های WW و WD به صورت سلسله مراتبی، برای دو تراکنش.. 77

شکل 6-1- مقایسه تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل‌های 2PL، WW و WD.. 82

شکل 6-2- مقایسه تعداد گام‌های اجرای تراکنش‌های کوچک در مدل‌های 2PL، WW و WD.. 87

شکل 6-3- مقایسه تعداد گام‌های اجرای تراکنش‌های بزرگ در مدل‌های 2PL، WW و WD.. 87

شکل 6-4- مقایسه تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل‌های 2PL، WW و WD.. 91

شکل 6-5- مقایسه تعداد گام‌های تراکنش‌ها با تعداد کم و زیاد داده‌های مشترک (بدون داده غیر مشترک) در مدل‌های 2PL، WW و WD   96

 

 

 

 

 

 

 

 

 

 

فصل اول

 

مقدمه

 

 

1-1-           مقدمه

اجرای همروند تراکنش‌ها در پایگاه داده‌ها با مشکلات بسیاری مواجه است. مکانیزم‌های کنترل همروندی، برای حفظ انزوا و عدم دخالت اجرا در میان تراکنش‌های متعارض و حفظ سازگاری پایگاه داده‌ها استفاده می‌شوند (a-Pashazadeh, 2012)، (b-Pashazadeh, 2012) و (Shu, and Young, 2002). به عبارت دیگر الگوریتم‌های کنترل همروندی، الگوریتم‌هایی هستند که باعث می‌شوند اجرای همروند چند تراکنش و اجرای متوالی آن معادل شود. مسئله‌ی کنترل همروندی در پایگاه داده‎ها امری ضروری و با اهمیت می‎باشد (Shu, and Young, 2002). در این زمینه مطالعات و تحقیقات فراوانی صورت گرفته است که نتیجه‌ی آن، به وجود آمدن الگوریتم‌های متنوع کنترل همروندی می‎باشد. همچنین با توجه به گسترش روزافزون انواع پایگاه داده‌ها در سراسر جهان، نیاز به بررسی پروتکل‌های کنترل همروندی پایگاه داده‌ها، بیشتر نمایان می‌شود.

مدل‌سازی رسمی[1] از الگوریتم‌های کنترل همروندی در مطالعه ویژگی‌های مختلف آن‌ها بسیار مفید است (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012). بررسی‌ها نشان می‌دهد که شبکه‌های پتری (PNs)[2] روش مناسبی برای مدل‌سازی رسمی مکانیزم‌های کنترل همروندی می‌باشند. شبکه‌های پتری انواع مختلفی دارند که یکی از آن‌ها شبکه‌ پتری رنگی (CPN)[3] است. شبکه‌های پتری رنگی یکی از بهترین ابزارها برای مدل‌سازی الگوریتم‌های کنترل همروندی هستند (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012). به همین دلیل در این پایان‌نامه نیز از این روش برای مدل‌سازی‌ها استفاده خواهد شد.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 896

|

امتیاز مطلب : 0

|

تعداد امتیازدهندگان : 0

|

مجموع امتیاز : 0